package com.lcm.algorithm.datatest.greedy;

import java.util.Arrays;

/**
 * @description:
 * @author: lcm
 * @create: 2020-04-10 13:50
 **/

public class Candy {

    public static void main(String[] args){

    }

    public static int candy(int[] ratings) {
        int[] array=new int[ratings.length];
        array[0]=1;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                array[i]=array[i-1]+1;
            }else{
                array[i]=1;
            }
        }
        int result=array[ratings.length-1];
        for (int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]&&array[i]<=array[i+1]){
                array[i]=array[i+1]+1;
            }
            result=result+array[i];
        }
        return result;
    }

    /**
     * 暴力解法
     * @param ratings
     * @return
     */
    public int candy1(int[] ratings) {
        int[] num=new int[ratings.length];
        Arrays.fill(num,1);
        boolean b=true;
        while (b){
            b=false;
            for(int k=0;k<ratings.length-1;k++){
                if((ratings[k]>ratings[k+1])&&(num[k]<=num[k+1])){
                    num[k]=num[k+1]+1;
                    b=true;
                }
            }
            for(int j=ratings.length-1;j>0;j--){
                if((ratings[j]>ratings[j-1])&&(num[j]<=num[j-1])){
                    num[j]=num[j-1]+1;
                    b=true;
                }
            }
        }
        int sum=0;
        for(int i=0;i<num.length;i++){
            sum=sum+num[i];
        }
        return sum;
    }
}
